[开学考试]最大平方数

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

给出 $N$ ,求 $1$ 到 $N$ 个数中选出任意个数相乘能组成的最大平方数,由
于此数可能很大,你只需要输出此数除 $100000007$ 的余数即可。

样例输入

1
7

样例输出

1
144

样例解释

$2\times 3 \times 4\times 6=144$

数据下载

由于各大oj可能没有，故在此提供测试数据

题解

题目就是这么简单，然而考试并没有想到$QAQ$
因为是任意个数相乘，我们可以将$N!$进行质因数分解
然后因为$A^2\times B^2=(A\times B)^2$
我们就可以把所有的2的整数倍次方全部乘入答案里，就是最大的平方数。

而普通的方法分解$N!$需要$O(N\sqrt{N})$的时间复杂度，我们可以考虑一种新方法。

显然，$N!$的每个质因子都不会超过$N$，我们可以先筛选出$1-N$的每个质数$p$，然后考虑阶乘中一共包含多少个质因子$p$

$N!$中质因子$p$的个数就等于$1-N$每个数包含的质因子$p$的个数之和。在$1-N$中，$p$的倍数，即至少包含1个质因子$p$的显然有$\lfloor N/p \rfloor$个。而$p^2$的倍数，即至少包含2个质因子$p$的有$\lfloor N/p^2 \rfloor$个。不过其中的一个质因子已经在$\lfloor N/p \rfloor$中统计过，所以只需要再统计第2个质因子，即累加上$\lfloor N/p^2 \rfloor$，而不是$2\times \lfloor N/p^2 \rfloor$

综上所述，$N!$中质因子$p$的个数为：

$$ \left\lfloor \dfrac{N}{P} \right\rfloor+\left\lfloor \dfrac{N}{P^2} \right\rfloor+\left\lfloor \dfrac{N}{P^3} \right\rfloor+\dots+\left\lfloor \frac{N}{P^{\lfloor log_p N \rfloor}} \right\rfloor=\sum_{p^k\le N}\left\lfloor \dfrac{N}{P^k} \right\rfloor $$

上面的计算只需要$O(logN)$的时间
整个过程只需要$O(NlogN)$的时间

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int mod=100000007;
int n,ans=1;
bool v[10000010];
vector<int> prime;

void get_prime(int n){
    for(int i=2;i<=n;i++){
        if(v[i])continue;
        prime.push_back(i);
        for(int j=i;j<=n/i;j++)v[i*j]=1;
    }
}

int main(){
    cin>>n;
    get_prime(n);
    for(int i=0;i<prime.size();i++){
        int p=prime[i],c=0;
        for(int j=n;j;j/=p)c+=j/p;
        if(c==0)continue;
        if(c&1){
            for(int i=1;i<c;i++)ans=(long long)ans*p%mod;//这里要么取两次mod，要么用long long，后者快一点，当然可以用快速幂，更快（我懒orz
        }
        else for(int i=1;i<=c;i++)ans=(long long)ans*p%mod;//这里要么取两次mod，要么用long long，后者快一点，当然可以用快速幂，更快
    }
    cout<<ans;
    return 0;
}